//回文子串
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n,vector<bool>(n));
        int ret = 0;
        for(int i = n-1 ; i >= 0 ; --i)
        {
            for(int j = i ; j < n ; ++j)
            {
                if(s[i] == s[j])
                    dp[i][j] = i+1 < j ? dp[i+1][j-1] : true;

                if(dp[i][j]) ret++;
            }
        }
        return ret;
    }
};

//最长回文子串
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n,vector<bool>(n));
        int ret_start = 0;
        int ret_end = 0;
        for(int i = n-1 ; i >= 0 ; --i)
        {
            for(int j = i ; j < n ; ++j)
            {
                if(s[i] == s[j])
                    dp[i][j] = i+1 < j ? dp[i+1][j-1] : true;

                if(dp[i][j] == true && ret_end - ret_start < j-i)
                {
                    ret_start = i;
                    ret_end = j;
                }
            }
        }
        std::cout << ret_start << " " << ret_end << std::endl;
        string ret(s.begin()+ret_start,s.begin()+ret_end+1);
        return ret;
    }
};

//分割回文串IV
class Solution {
public:
    bool checkPartitioning(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n,vector<bool>(n));
        for(int i = n-1 ; i >= 0 ; --i)
        {
            for(int j = i ; j < n ; ++j)
            {
                if(s[i] == s[j])
                    dp[i][j] = i+1 < j ? dp[i+1][j-1] : true;

            }
        }
        for(int i = 1 ; i < n ; ++i)
        {
            for(int j = 0 ; j < n-1 ;++j)
            {
                if(dp[i][j] && dp[0][i-1] && dp[j+1][n-1])
                    return true;
            }
        }
        return false;
    }
};







